#pragma once

#include <deque>
#include <utility>
#include <vector>

namespace jianzhi_013
{

class Solution
{
public:
    int movingCount(int m, int n, int k)
    {
        std::vector row_sum(m, 0);
        for (int i = 0, r_sum = 0; i < m; ++i) {
            if (i % 10 == 0) {
                r_sum = 0;
                for (int r = i; r != 0; r /= 10)
                    r_sum += r % 10;
            }
            row_sum.at(i) = r_sum;
            ++r_sum;
        }

        std::vector col_sum(n, 0);
        for (int i = 0, c_sum = 0; i < n; ++i) {
            if (i % 10 == 0) {
                c_sum = 0;
                for (int c = i; c != 0; c /= 10)
                    c_sum += c % 10;
            }
            col_sum.at(i) = c_sum;
            ++c_sum;
        }

        int num_visited = 0;
        std::vector<unsigned char> visited(m * n, 0);
        std::deque< std::pair<int, int> > queue;

        auto visit = [&](int r, int c) {
            if (r < 0 || r >= m || c < 0 || c >= n)
                return;
            if (row_sum.at(r) + col_sum.at(c) > k)
                return;
            if (visited.at(r * n + c))
                return;
            ++num_visited;
            visited.at(r * n + c) = 1;
            queue.emplace_back(r, c);
        };

        visit(0, 0);
        while (!queue.empty()) {
            auto [r, c] = queue.front();
            queue.pop_front();
            visit(r - 1, c);
            visit(r + 1, c);
            visit(r, c - 1);
            visit(r, c + 1);
        }
        return num_visited;
    }
};

}  /* namespace jianzhi_013 */
